#include "headfiles.h"

using namespace std;

string longestPalindromeString(string &str) {
    if (str.size() <= 1) {
        return str;
    }

    size_t size = str.size();
    bool *table = (bool *)malloc(size * size);
    if (table == NULL) {
        return string("");
    }
    memset(table, 0, sizeof(bool) * size * size);

    size_t i, j, loc, len;
    size_t max_len, max_i;
    for (i = 0; i < size; i++) {
        loc = i * size + i;
        table[loc] = true;
        max_i = i;
        max_len = 1;
    }

    for (i = 0; i < size - 1; i++) {
        if (str[i] == str[i + 1]) {
            loc = i * size + i + 1;
            table[loc] = true;
            max_len = 2;
            max_i = i;
        }
    }

    for (len = 3; len <= size; len++) {
        for (i = 0; i < size - len + 1; i++) {
            j = i + len - 1;
            loc = (i + 1) * size + j - 1;
            if (str[i] == str[j] && table[loc] == true) {
                loc = i * size + j;
                table[loc] = true;
                max_i = i;
                max_len = len;
                cout << "max_i = " << max_i << "max_len = " << max_len << endl;
            }
        }
    }

    return str.substr(max_i, max_len);
}

string longestPalindromeString1(string &str) {
    size_t i, j;
    size_t max_i, max_len;
    size_t str_size = str.size();

    // Odd number of characters case
    max_i = 0;
    max_len = 1;
    for (i = 0; i < str_size; i++) {
        for (j = i - 1; j >= 0; j--) {
            size_t k = i + (i - j);
            if (k < str_size && str[j] == str[k]) {
                if (max_len < 2 * (i - j) + 1) {
                    max_len = 2 * (i - j) + 1;
                    max_i = j;
                }
            }
            else {
                break;
            }
        }
    }

    for (i = 0; i < str_size - 1; i++) {
        if (str[i] == str[i + 1]) {
            for (j = i - 1; j >= 0; j--) {
                size_t k = i + 1 + (i - j);
                if (k < str_size && str[j] == str[k]) {
                    if (max_len < 2 * (i - j) + 2) {
                        max_len = 2 * (i - j) + 2;
                        max_i = j;
                    }
                }
                else {
                    break;
                }
            }
        }
    }

    return str.substr(max_i, max_len);
}

